import java.util.NoSuchElementException;

public class MaxPQ {
    private state[] pq;                    // store items at indices 1 to N
    private int N;                       // number of items on priority queue


   /**
     * Create a priority queue with the given items.
     */
    public MaxPQ(state[] keys) {
        N = keys.length;
        pq = new state[keys.length + 1]; 
        for (int i = 0; i < N; i++) {
            pq[i+1] = keys[i];
        } 
        for (int k = N/2; k >= 1; k--) {
            sink(k);
        }
    }
   /**
     * Is the priority queue empty?
     */
    public boolean isEmpty() {
        return N == 0;
    }

   /**
     * Return the number of items on the priority queue.
     */
    public int size() {
        return N;
    }

   /**
     * Return the largest key on the priority queue.
     * Throw an exception if the priority queue is empty.
     */
    public state max() {
        if (isEmpty()) throw new RuntimeException("Priority queue underflow");
        return pq[1];
    }

    // helper function to double the size of the heap array
    private void resize(int capacity) {
        assert capacity > N;
        state[] temp = new state[capacity];
        for (int i = 1; i <= N; i++) temp[i] = pq[i];
        pq = temp;
    }


   /**
     * Add a new key to the priority queue.
     */
    public void insert(state x) {

        // double size of array if necessary
        if (N >= pq.length - 1) resize(2 * pq.length);
        // add x, and percolate it up to maintain heap invariant
        pq[++N] = x;
        swim(N);
    }

   /**
     * Delete and return the largest key on the priority queue.
     * Throw an exception if the priority queue is empty.
     */
    public state delMax() {
        if (N == 0) throw new RuntimeException("Priority queue underflow");
        state max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;     // to avoid loiterig and help with garbage collection
        if ((N > 0) && (N == (pq.length - 1) / 4)) resize(pq.length / 2);
        return max;
    }


   /***********************************************************************
    * Helper functions to restore the heap invariant.
    **********************************************************************/

    private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }

    private void sink(int k) {
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

   /***********************************************************************
    * Helper functions for compares and swaps.
    **********************************************************************/
    public boolean less(int i, int j) {
        return (pq[i].getCalpop() < pq[j].getCalpop());
    }

    private void exch(int i, int j) {
        state swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
    }
}
